import java.text.*;
import java.util.*;
import java.io.*;

public class Backward extends MarkovModelAlgo {

  double[][] b;

  public Backward(HMM hmm, Object x[]) {
    super(hmm, x);
    int L = x.length;
    b = new double[L+1][hmm.nstate];
    for (int k=1; k<hmm.nstate; k++) b[L][k] = 0;
    for (int i=L-1; i>=1; i--)
      for (int k=0; k<hmm.nstate; k++) {
        double sum = Double.NEGATIVE_INFINITY;
        for (int ell=1; ell<hmm.nstate; ell++) sum = logplus(sum, hmm.loga[k][ell] + hmm.loge[ell][hmm.getSym(x[i])] + b[i+1][ell]);
        b[i][k] = sum;
      }
  }

  double logprob() {
    double sum = Double.NEGATIVE_INFINITY;
    for (int ell=0; ell<((HMM)mm).nstate; ell++) 
      sum = logplus(sum,   ((HMM)mm).loga[0][ell] 
                         + ((HMM)mm).loge[ell][mm.getSym(x[0])] 
                         + b[1][ell]);
    return sum;
  }

  public void print(PrintStream out) {
    int nstate = ( mm instanceof HMM ) ? ((HMM)mm).nstate : 1;
    for (int j=0; j<nstate; j++) {
      for (int i=0; i<b.length; i++) out.print(MarkovModel.fmtlog(b[i][j]));
      out.println();
    }
  }

}
